package exercisesdemo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-10
 * Time: 22:14
 */

/**
 * 描述:
 * 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
 * 且不能改变原来的数据顺序，返回重新排列后的链表的头指针
 */
public class Exercise1 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode pHead, int x) {
        // write code here

        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;

        while (cur != null) {
            if (cur.val > x) {
                //第一次插入
                if (as == null) {
                    as = ae = cur;
                }else {//第N次插入

                    ae.next = cur;
                    ae = ae.next;
                }
            } else {
                //第一次插入
                if (bs == null) {
                    bs = be = cur;
                }else{//第N次插入
                    be.next = cur;
                    be = be.next;
                }
            }

            cur = cur.next;
        }

        //当一个链表为空时，返回
        if(as == null) {
            return bs;
        }


        //如果到这里as!= null
        //连接两部分
        ae.next = bs;

        //注意，第二部分为空时，要手动把第二部分最后一个节点，手动制空
        if(bs != null) {
            be.next = null;
        }

        //最后返回as
        return as;
    }
}
